package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

/**
 * @author tzp
 * @since 2020/9/15
 */
public class LC63 implements DynamicProblem {

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid == null || obstacleGrid.length == 0) return 0;
        int lrow = obstacleGrid.length;
        int lcol = obstacleGrid[0].length;

        int[][] state = new int[lrow][lcol];

        for (int i = lrow - 1; i >= 0; i--) {
            for (int j = lcol - 1; j >= 0; j--) {
                if (i == lrow - 1 && j == lcol - 1) {
                    state[i][j] = obstacleGrid[i][j] == 1 ? 0 : 1;
                } else {
                    if (obstacleGrid[i][j] == 1) {
                        state[i][j] = 0;
                    } else {
                        int sum = 0;
                        if (i + 1 < lrow) {
                            sum += state[i + 1][j];
                        }
                        if (j + 1 < lcol) {
                            sum += state[i][j + 1];
                        }
                        state[i][j] = sum;
                    }
                }
            }
        }
        return state[0][0];
    }

    public static void main(String[] args) {
        int[][] a = {{0, 0, 0}, {0, 1, 0}, {0, 0, 0}};
        System.out.println(new LC63().uniquePathsWithObstacles(a));
    }
}
